package com.leetcode.algorithm.y19.m04;

import java.util.Arrays;

/**
 * leetcode-cn.com
 * 
 * (done)718. 最长重复子数组
 * (done)198. 打家劫舍
 * (done)213. 打家劫舍 II
 * @author: jie.deng
 * @time: 2019年4月5日 下午8:15:15
 */
public class MySolution0405 {
    
    /**
     * 718. 最长重复子数组
     * 
	 * 给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。
	 * 
	 * 示例 1:
	 * 
	 * 输入:
	 * A: [1,2,3,2,1]
	 * B: [3,2,1,4,7]
	 * 输出: 3
	 * 解释: 
	 * 长度最长的公共子数组是 [3, 2, 1]。
	 * 说明:
	 * 
	 * 1 <= len(A), len(B) <= 1000
	 * 0 <= A[i], B[i] < 100
     * @param A
     * @param B
     * @return
     */
    public int findLength(int[] A, int[] B) {
        // 动态规划-最长公共子串类似的解法
        int max = 0;
        int bLen = B.length;
        int aLen = A.length;
        int[][] table = new int[bLen][aLen];
        int b0 = B[0];
        for (int i = 0; i < aLen; i++) {
            if (A[i] == b0) {
                table[0][i] = 1;
                max = 1;
            }
        }
        int a0 = A[0];
        for (int i = 1; i < bLen; i++) {
            if (a0 == B[i]) {
                table[i][0] = 1;
                max = 1;
            }
        }
        for (int i = 1; i < bLen; i++) {
            int bi = B[i];
            for (int j = 1; j < aLen; j++) {
                if (bi == A[j]) {
                    table[i][j] = table[i - 1][j - 1] + 1;
                    if (table[i][j] > max) {
                        max = table[i][j];
                    }
                }
            }
        }
        return max;
    }
    
    /**
     * 198. 打家劫舍
     * 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
     * 给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
     *
     *  示例 1:
     *  输入: [1,2,3,1]
     *  输出: 4
     *  解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。偷窃到的最高金额 = 1 + 3 = 4 。
     *  
     *  示例 2:
     *  输入: [2,7,9,3,1]
     *  输出: 12
     *  解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。偷窃到的最高金额 = = 2 + 9 + 1 = 12 。
     *
     * @param nums
     * @return
     */
    public int rob(int[] nums) {
        // 动态规划
        int len = nums.length;
        if (len == 0) {
            return 0;
        }
        if (len == 1) {
            return nums[0];
        }
        nums[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < len; i++) {
            nums[i] = Math.max(nums[i - 1], nums[i - 2] + nums[i]);
        }
        return nums[len - 1];
    }
    
    /**
     * 213. 打家劫舍 II
     * 
	 * 你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
	 * 
	 * 给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
	 * 
	 * 示例 1:
	 * 
	 * 输入: [2,3,2]
	 * 输出: 3
	 * 解释: 你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
	 * 示例 2:
	 * 
	 * 输入: [1,2,3,1]
	 * 输出: 4
	 * 解释: 你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。偷窃到的最高金额 = 1 + 3 = 4 。
     * @param nums
     * @return
     */
    public int robII(int[] nums) {
        // 动态规划
        int len = nums.length;
        if (len == 0) {
            return 0;
        }
        if (len == 1) {
            return nums[0];
        }
        // 偷窃0号房屋,不偷窃最后一号房屋可得的最大金额
        int n = rob(Arrays.copyOfRange(nums, 0, nums.length - 1));
        // 不偷窃0号房屋可得的金额
        int m = rob(Arrays.copyOfRange(nums, 1, nums.length));
        return Math.max(m, n);
    }
}
